/***
 * 二分查找
 * 57.和为s的两个数字
 * 53.I.在排序数组中查找数字I
 * 11.旋转数组中的最小数字
 * 53.II.0~n-1中缺失的数字
 * 04.二维数组中的查找
 * **/

#include <iostream>
#include <unordered_map>
#include <vector>
using std::cout;
using std::endl;
using std::unordered_map;
using std::vector;

template <class T>
void print(const T &t)
{
    class T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
#if 0
    vector<int> twoSum(vector<int> &nums, int target)
    {
        // 写一下二分吧 O(NlogN)
        for (int i = 0; i < nums.size() - 1; ++i) {
            // 二分
            int left = i + 1, right = nums.size() - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target - nums[i]) {
                    return {nums[i], nums[mid]};
                } else if (nums[mid] < target - nums[i]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            // left > right 没找到
            // do nothing
        }
        return {};
    }
#endif
#if 0
    vector<int> twoSum(vector<int> &nums, int target)
    {
        // 既然提到hash，就写一下
        // 采坑一： 先查表再加表，否则存在“我查我自己”的问题
        unordered_map<int, int> hashMap;
        for (int &num: nums){
            if (hashMap.count(target - num)){
                return {num, target - num};
            }
            hashMap[num] = target - num;
        }
        return {};
    }
#endif
    vector<int> twoSum(vector<int> &nums, int target)
    {
        // 二分非最优解 无序用打表 有序双指针
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            int sum = nums[i] + nums[j];
            if (sum == target) {
                return {nums[i], nums[j]};
            } else if (sum < target) {
                ++i;
            } else {
                --j;
            }
        }
        return {};
    }
    // 53.I 同LeetCode34.
    int searchInsert(vector<int> &nums, int target)
    {
        // 返回target左边界，若无则返回插入位置
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 即使是查到的情况下right仍然执行mid-1，所以最终的right必是小于target
        // left > right
        return left;
    }
    int search(vector<int> &nums, int target)
    {
        int leftIdx = searchInsert(nums, target);
        int rightIdx = searchInsert(nums, target + 1) - 1;
        return rightIdx - leftIdx + 1;
    }
    // 11.
    int minArray(vector<int> &numbers)
    {
        // 二分
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 去右半边
            if (numbers[mid] > numbers[right]) {
                left = mid + 1;
                // 去左半边
            } else if (numbers[mid] > numbers[right]) {
                right = mid;
                // nums[mid]==nums[right]时无法决定去哪个半区间
                // 但是不要慌，左闭右开区间的二分查找确定了left<right,
                // mid也一定小于right，因此可以忽略右端点
            } else {
                --right;
            }
        }
        return numbers[left];
    }
    // 53.
    int missingNumber(vector<int> &nums)
    {
        // nums[i] == i
        int n = nums.size();
        if (nums[0] != 0) {
            return 0;
        }
        if (nums[n - 1] != n) {
            return n;
        }
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == mid) {
                // 去右半区间
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // left == right
        return left;
    }
    // 04.
    bool findNumberIn2DArray(vector<vector<int>> &matrix, int target)
    {
        // 从右上往左下查 O(N+M) 不会漏解
        if (matrix.empty())
            return false;
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) { // 小了，往下走
                ++i;
            } else { // 大了，往左走
                --j;
            }
        }
        return false;
    }
};

Solution solve = Solution();

void test57()
{
    vector<int> nums = {16, 16, 18, 24, 30, 32};
    int target = 48;
    print(solve.twoSum(nums, target));
}
void test53I()
{
    vector<int> nums = {1, 2, 3};
    int target = 1;
    cout << solve.search(nums, target) << endl;
}
void test11()
{
    vector<int> nums = {3, 4, 5, 1, 2};
    cout << solve.minArray(nums) << endl;
}
void test53II()
{
    vector<int> nums = {0, 2, 3};
    cout << solve.missingNumber(nums) << endl;
}
void test04()
{
    vector<vector<int>> matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
    int target = 18;
    cout << solve.findNumberIn2DArray(matrix, target) << endl;
}

int main()
{
    // test57();
    // test53I();
    // test11();
    // test53II();
    test04();

    return 0;
}